import java.util.*;
public class Main {

    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}

/*
* 二叉树上有 n 个节点，按从0到 n - 1 编号，其中节点i的两个子节点分别是 leftChild[i] 和  rightChild[i]。
只有所有节点能够形成且只形成一颗有效的二叉树时，返回 true；否则返回 false。
如果节点i没有左子节点，那么 leftChild[i] 就等于-1。右子节点也符合该规则。
注意：节点没有值，本问题中仅仅使用节点编号。
例如；输入：n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
输出：true
* */
class Solution {
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        // 创建一个Set用于存储已经访问过的节点
        Set<Integer> visited = new HashSet<>();

        // 遍历所有节点
        for (int i = 0; i < n; i++) {
            // 检查当前节点是否已经被访问过，如果访问过则说明形成了环，返回false
            if (visited.contains(i))
                return false;

            // 访问当前节点
            visited.add(i);

            // 获取当前节点的左子节点和右子节点
            int left = leftChild[i];
            int right = rightChild[i];

            // 检查左子节点
            if (left != -1) {
                // 检查左子节点是否已经被访问过，如果访问过则说明存在重复访问，返回false
                if (visited.contains(left))
                    return false;

                // 访问左子节点
                visited.add(left);
            }

            // 检查右子节点
            if (right != -1) {
                // 检查右子节点是否已经被访问过，如果访问过则说明存在重复访问，返回false
                if (visited.contains(right))
                    return false;

                // 访问右子节点
                visited.add(right);
            }
        }

        // 最后检查是否有孤立的节点，即节点未被访问过，返回false
        return visited.size() == n;
    }
}
/*这个解决方案使用了一个Set数据结构来存储已经访问过的节点。首先遍历所有节点，对于每个节点
，检查其是否已经被访问过，如果已经访问过，说明存在环，返回false。然后访问当前节点，并检查其左子节点和右子节点，
如果子节点已经被访问过，说明存在重复访问，返回false。最后检查是否有孤立的节点，即节点未被访问过，如果存在孤立节点，
返回false。如果所有节点都满足条件，返回true。*/
/*
*
* 解答错误
24 / 43 个通过的测试用例
输入
n =
4
leftChild =
[1,-1,3,-1]
rightChild =
[2,-1,-1,-1]
添加到测试用例
输出
false
预期结果
true
* */

/*
* 我检查了一下代码，发现我没有考虑到根节点的情况。
* 根节点应该是没有父节点的，但是在原来的实现中没有对根节点进行判断。下面是修复后的代码：
* */
class Solution2 {
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        // 创建一个Set用于存储已经访问过的节点
        Set<Integer> visited = new HashSet<>();

        // 记录节点的父节点
        int[] parent = new int[n];
        Arrays.fill(parent, -1);

        // 遍历所有节点
        for (int i = 0; i < n; i++) {
            // 检查当前节点是否已经被访问过，如果访问过则说明形成了环，返回false
            if (visited.contains(i))
                return false;

            // 访问当前节点
            visited.add(i);

            // 获取当前节点的左子节点和右子节点
            int left = leftChild[i];
            int right = rightChild[i];

            // 检查左子节点
            if (left != -1) {
                // 检查左子节点是否已经被访问过，如果访问过则说明存在重复访问，返回false
                if (visited.contains(left))
                    return false;

                // 检查左子节点是否已经有父节点，如果有，则返回false
                if (parent[left] != -1)
                    return false;

                // 记录左子节点的父节点
                parent[left] = i;

                // 访问左子节点
                visited.add(left);
            }

            // 检查右子节点
            if (right != -1) {
                // 检查右子节点是否已经被访问过，如果访问过则说明存在重复访问，返回false
                if (visited.contains(right))
                    return false;

                // 检查右子节点是否已经有父节点，如果有，则返回false
                if (parent[right] != -1)
                    return false;

                // 记录右子节点的父节点
                parent[right] = i;

                // 访问右子节点
                visited.add(right);
            }
        }

        // 最后检查是否有孤立的节点，即节点未被访问过，返回false
        return visited.size() == n;
    }
}

/*
*
* 解答错误
24 / 43 个通过的测试用例
输入
n =
4
leftChild =
[1,-1,3,-1]
rightChild =
[2,-1,-1,-1]
添加到测试用例
输出
false
预期结果
true
* */


/*
* 经过仔细检查，我发现在判断孤立节点的部分出现了问题。
* 孤立节点是指没有父节点的节点，但是在原来的实现中没有正确地进行判断。下面是修复后的代码：
* */

class Solution3 {
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        // 记录节点的入度
        int[] inDegree = new int[n];

        // 遍历所有节点
        for (int i = 0; i < n; i++) {
            int left = leftChild[i];
            int right = rightChild[i];

            // 检查左子节点
            if (left != -1) {
                // 左子节点的入度加1
                inDegree[left]++;

                // 如果左子节点的入度大于1，说明存在多个父节点，返回false
                if (inDegree[left] > 1)
                    return false;
            }

            // 检查右子节点
            if (right != -1) {
                // 右子节点的入度加1
                inDegree[right]++;

                // 如果右子节点的入度大于1，说明存在多个父节点，返回false
                if (inDegree[right] > 1)
                    return false;
            }
        }

        // 统计入度为0的节点个数
        int rootCount = 0;
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0)
                rootCount++;
            // 如果有多个入度为0的节点，说明存在多个根节点，返回false
            if (rootCount > 1)
                return false;
        }

        // 如果没有入度为0的节点，说明存在环或有孤立节点，返回false
        if (rootCount == 0)
            return false;

        // 如果所有节点都满足条件，返回true
        return true;
    }
}

/*
 * 这次的修复主要针对孤立节点和根节点进行了判断。通过记录每个节点的入度，然后统计入度为0的节点个数，如果入度为0的节点个数不为1，
 * 说明存在多个根节点，返回false；如果入度为0的节点个数为0，说明存在环或有孤立节点，返回false。如果所有节点都满足条件，返回true。
 * */

/*
* 解答错误
39 / 43 个通过的测试用例
输入
n =
4
leftChild =
[1,0,3,-1]
rightChild =
[-1,-1,-1,-1]
添加到测试用例
输出
true
预期结果
false
* */

/*
在修复过程中，我没有考虑到二叉树的根节点应该有且只有一个，
但是在原来的实现中没有对根节点个数进行判断。下面是修复后的代码：
* */

class Solution4 {
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        // 记录节点的入度
        int[] inDegree = new int[n];

        // 遍历所有节点
        for (int i = 0; i < n; i++) {
            int left = leftChild[i];
            int right = rightChild[i];

            // 检查左子节点
            if (left != -1) {
                // 左子节点的入度加1
                inDegree[left]++;

                // 如果左子节点的入度大于1，说明存在多个父节点，返回false
                if (inDegree[left] > 1)
                    return false;
            }

            // 检查右子节点
            if (right != -1) {
                // 右子节点的入度加1
                inDegree[right]++;

                // 如果右子节点的入度大于1，说明存在多个父节点，返回false
                if (inDegree[right] > 1)
                    return false;
            }
        }

        // 统计入度为0的节点个数和根节点
        int rootCount = 0;
        int rootNode = -1;
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                rootCount++;
                rootNode = i;
            }
            // 如果有多个入度为0的节点，说明存在多个根节点，返回false
            if (rootCount > 1)
                return false;
        }

        // 如果没有入度为0的节点，说明存在环或有孤立节点，返回false
        if (rootCount == 0)
            return false;

        // 检查是否能够遍历到所有节点
        Set<Integer> visited = new HashSet<>();
        if (!dfs(rootNode, leftChild, rightChild, visited))
            return false;

        // 如果所有节点都满足条件，返回true
        return visited.size() == n;
    }

    private boolean dfs(int node, int[] leftChild, int[] rightChild, Set<Integer> visited) {
        if (node == -1)
            return true;

        // 检查当前节点是否已经被访问过，如果访问过则说明形成了环，返回false
        if (visited.contains(node))
            return false;

        // 访问当前节点
        visited.add(node);

        // 递归遍历左子节点和右子节点
        return dfs(leftChild[node], leftChild, rightChild, visited) && dfs(rightChild[node], leftChild, rightChild, visited);
    }
}

/*
 * 修复后的代码在判断根节点个数时引入了一个变量rootNode，用于记录入度为0的节点的编号。然后在检查是否能够遍历到所有节点时，
 * 使用DFS遍历二叉树，检查节点是否已经访问过，如果已经访问过，说明存在环，返回false。如果所有节点都满足条件，返回true。
 * */


/*二叉树剪枝
给定一个二叉树根节点root，树的每个节点的值要么是0，要么是1。请剪除该二叉树中所有节点的值为0的子树。
节点node的子树为node本身，以及所有node的后代。
* */



  class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

class Solution5 {
    public TreeNode pruneTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        // 递归剪枝左子树和右子树
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);

        // 如果当前节点的值为0且左右子树都为空，则将当前节点剪除
        if (root.val == 0 && root.left == null && root.right == null) {
            return null;
        }

        return root;
    }
}